CODv2 第3章「命令：マシンの言葉」

top

CODv2 第3章「命令：マシンの言葉」

CODv2 3.1 はじめに

命令( instruction )

命令セット( instruction set )

CODv2 3.2 コンピュータ・ハードウェアの演算

MIPS のアセンブリ言語での加算

a = b + c

2つの変数 b と c を加えて、その和を a に収めることを意味する

code:1.asm

add a, b, c

a = b + c + d + e

code:2.asm

add a, b, c

add a, a, d

add a, a, e

加算のような演算に必要なオペランド( operand )は、3つある。加算対象の2つの数と和を収める変数である。すべての命令がオペランドの数を必ず3つにすれば、ハードウェアの単純性を保つという理念にかなう。

設計原則1

単純性は規則性につながる

table:算術演算

命令 例 意味 備考

add add a, b, c a = b + c 常に3オペランド

subtract sub a, b, c a = b - c 常に3オペランド

code:exp3.2.1.c

a = b + c;

d = a - e;

code:exp3.2.1.asm

add a, b, c

sub d, a, e

code:exp3.2.2.c

f = (g + h) - (i + j);

code:exp3.2.2.asm

add t0, g, h

add t1, i, j

sub f, t0, t1

コンパイラは t0, t1 という一時的な変数を生成する

これらの命令は MIPS プロセッサが実際に理解するコードを記号(シンボル)で表記したもの。このシンボル表記を MIPS の実際の言語へと発展させ、順を追ってシンボル表記もより具体化していく

CODv2 3.3 コンピュータ・ハードウェアのオペランド

レジスタには限りがある。レジスタはハードウェアを構成する基本要素であり、プログラマ側からも見える。

MIPS アーキテクチャにおいいては、レジスタ長は32ビットである。32ビットをひとまとめにしたものを1つの単位として語( word )と呼ぶ

レジスタ長は 32bit ( 4Byte )

プログラミング言語の変数とレジスタの間の違いのひとつに、レジスタの数は限られている点が挙げられる。MIPS には32個のレジスタが用意されている

レジスタ数は 32個

シンボル表記を MIPS の言語へと順を追って発展させるにあたり制限を加える

MIPS の算術演算命令の3つのオペランドには32個あるレジスタのどれかを当てなければならない

レジスタ数に限りがある理由は基本原則による

設計原則2

小さければ小さいほど高速になる

code:exp3.3.1.c

f = (g + h) - (i + j);

変数 f, g, h, i, j をそれぞれレジスタの $s0, $s1, $s2, $s3, $s4 に割り付けるとする

table:register

f $s0

g $s1

h $s2

i $s3

j $s4

一時レジスタ $t0, $t1 を割り当てる

code:exp3.3.1.asm

add $t0, $s1, $s2

add $t1, $s3, $s4

sub $s0, $t0, $t1

この例では、変数が単一のデータ要素を表すという単純なものである

変数が配列というもっと複雑な形をとることもある。配列に含まれるデータ要素の数がレジスタの数を超えることがある。その場合はどのようにデータを表し、どのようにそれにアクセスしたらよいか

コンピュータの5つの要素

プロセッサがレジスタに格納できるデータ量はわずかであるが、メモリには莫大な量のデータを記憶できる

データ転送

MIPS マシンでは算術演算は必ずレジスタを用いて行われる

MIPS マシンにはメモリとレジスタの間でデータを転送する命令がそなわっていなければならない

そのような命令をデータ転送( data transfer )命令と呼ぶ

メモリ内の語にアクセスするためには、命令中でメモリのアドレス( address )を指定しなければならない。

ロード命令

メモリからレジスタへデータを転送するデータ転送命令を一般にロード( load )命令と呼ぶ

ロード命令の記述形式は以下の順である

レジスタ命令操作( operation )の名前

データをロードする先のレジスタ

メモリにアクセスするために使用する定数とレジスタ

配列要素のメモリ・アドレスは、命令の定数部分と2番目のレジスタの内容の和によって得られる

MIPS ではこの命令を lw ( load word )と呼ぶ

100語からなる配列 A

変数 g と h にレジスタ $s1 と $s2 を割り付ける

配列 A の開始アドレス(ベース・アドレス)( base address )はレジスタ $s3 中に収められている

code:exp3.3.2.c

この C のステートメントのアセンブラへの翻訳は

code:exp3.3.2.asm

データ転送命令中の定数をオフセット( offset )

1ワード(語)は4バイト

アドレスを得るために加えるレジスタをベース・レジスタ( base register )と呼ぶ

MIPS の実際のメモリとその内容

table:memory adress

adress data

... ...

12 100

8 10

4 101

0 1

8ビット( bit )

1バイト( byte )

語( data )は4バイトのサイズをもつ

語のアドレスは4バイトのうちの第1バイトのアドレスと等しい

MIPS では語アドレスは4の倍数でなければならない

この要件を整列化制約( alignment restriction )と呼ぶ

バイト・アドレスを採用しているマシンの2つのタイプ

ビッグ・エンディアン方式( big-endian )

リトル・エンディアン方式( little-endian )

数値の1番小さい桁1バイト分( "0A" )を、1番大きいアドレスの記憶装置( a )に配置し順に並べる規則をビッグエンディアンという。

数値の1番小さい桁1バイト分( "0A" )を、1番小さいアドレスの記憶装置( a + 3 )に配置し順に並べる規則をリトルエンディアンという。

https://gyazo.com/e7fda6e2432377bf4711ebd958772de5

MIPS はビッグ・エンディアン方式

ストア命令

ロード( load )と逆の命令をストア( store )と呼ぶ

ストア命令はレジシタからメモリへデータをデータ転送する

ストア命令の記述形式は以下の順である

レジスタ命令操作( operation )の名前

データをストアする元のレジスタ

配列要素を選択するためのオフセット、ベース・レジスタ

配列要素のメモリ・アドレスは、定数(オフセット)とレジスタ(配列要素の開始アドレス(ベース・アドレス))によって指定される

MIPS ではこの命令を sw ( store word )と呼ぶ

変数 h をレジスタ $s2 に割り付け

配列 A のベース・アドレスがレジスタ $s3 に収められている

code:exp3.3.3.c

code:exp.3.3.3.asm

この C の代入文には演算が1つしか含まれていない

しかしオペランドの2つがメモリ中にある

code:exp3.3.4.c

A は 100 の要素からなる配列

配列 A のベース・アドレスがレジスタ $s3 に収められている

コンパイラは変数 g, h, i をそれぞれレジスタ $s1, $s2, $s4 に割り付ける

整理すると

変数 g, h が $s1, $s2

配列 A のベース・アドレスが $s3

配列 A のインデックス i が $s4

配列 A のベースにインデックス i を加えてアドレスを得るまえにバイト・アドレス方式に対処するために i を4倍する(オフセットを合成する)

乗算命令は次章(4章)で説明する(エー?)

i を4倍するのと同等の効果を得る

まず最初に i と i を加算

i + i = 2i

次にその和をそれぞれ加算する

2i + 2i = 4i

code:exp3.3.4.asm

add $t1, $s4, $s4 # 2 * i の結果を一時レジスタ $t1 に代入

add $t1, $t1, $t1 # 4 * i の結果を一時レジスタ $t1 に代入(オフセットを合成)

スピル・アウト( spilling )

たいていのプログラムでは、マシンに備わっているレジスタの数よりも多くの変数が使用される

コンパイラは頻繁に使用される変数をレジスタに保持しておき、それ以外の変数をメモリ上に置こうとする

ロード命令とストア命令を使用してレジスタとメモリの間で変数をやりとりする

使用頻度の低い変数、後で必要となる変数をメモリ上に置くことを「スピル・アウト( spilling )する」という

データをレジスタに置いたほうが、アクセス速度は早い

レジスタはメモリよりも小さい

したがって、サイズと速度に関するハードウェアの原理から、メモリ・アクセスはレジスタ・アクセスよりも時間がかかる

データはレジスタにあった方が有用性が高まる

MIPS の演算命令(レジスタ上での演算)は、2つのレジスタを読んで、その内容に基づいて演算を行い、結果を書き込む

MIPS のデータ転送命令(メモリとレジスタ間のデータ転送)は、1つのオペランドを読み出すか、1つのオペランドを書き込むだけである

MIPS のレジスタには、アクセスに要する時間が短いと同時に、メモリよりスループットが高いという得難い特性がある

レジスタ中のデータは高速にアクセスできるだけでなく、容易に操作できる

最高の性能を発揮させるにはコンパイラはレジスタを効率よく使用しなければならない

この節で提示された MIPS アーキテクチャ

MIPS のオペランド

32個のレジスタ

$s0, $s1, $s2, ..., $s31 / $t0, $t1, $t2, ..., $t31

高速にアクセス可能なデータの格納場所

MIPS では演算の対象となるデータはレジスタに収めなければならない

2^30 のメモリ語

MIPSではデータ転送命令によってのみアクセスされる

バイト・アドレス方式を採っている

4バイト刻み

配列のようなデータ構造やスピル・アウトされたレジスタなどのデータを保持する

MIPS のアセンブリ言語

table:mips assembly language

区分 命令 例 意味 備考

算術演算 add add $s1, $s2, $s3 $s1 = $s2 + $s3 3オペランド、データはレジスタ中

算術演算 subtract sub $s1, $s2, $s3 $s1 = $s2 - $s3 3オペランド、データはレジスタ中

CODv2 3.4 コンピュータ内での命令の表現

10進数

decimal number

2進数

binary number

1bit

コンピュータ内では、命令も高低の電気信号系列で保持されるので、数値として表現することが可能

命令を構成するひとつひとつの信号は1個の数値とみなすことができる。よって、それらの数値を並べたものも命令とみなせる

レジスタはほとんどすべての命令で使用されるので、レジスタ名と番号を対応させる規約が欲しくなる

MIPS のアセンブリ言語では、

$s0 ~ $s7

レジスタの 16 から 23

8個の(?)レジスタ

$t0 ~ $t7

レジスタの 8 から 15

8個の一時レジスタ

に対応する

レジスタ数、32個の残りの部分に関する規約は、次の節にて説明する

code:exp3.4.1.asm

add $t0, $s1, $s2

レジスタ $t0 はレジスタ 8 を意味する

レジスタ $s1 はレジスタ 17 を意味する

レジスタ $s2 はレジスタ 18 を意味する

table:exp3.4.1.1

field No. 1 2 3 4 5 6

decimal 0 17 18 8 0 32

最初のフィールドと最後のフィールドの2つで、これが加算命令であることを表す

これを2進数で表現すると

table:exp3.4.1.2

field No. 1 2 3 4 5 6

binary 000000 10001 10010 01000 00000 100000

bit 6bit 5bit 5bit 5bit 5bit 6bit

機械語( machie language )

命令を数値で表現したものを、アセンブリ言語と区別して機械語( machie language )と呼ぶ

それらの命令を連ねたものをマシン・コード( machine code )と呼ぶ

命令を表記するこのような枠取りを命令形式( instruction format )と呼ぶ

MIPS 命令の長さは 32bit である( 6+5+5+5+6=32 )

1命令は1語から成る

MIPS の命令はすべて長さが 32bit となっている

table:exp3.4.1.3

field No. 1 2 3 4 5 6

filed name op rs rt rd shamt funct

bit 6bit 5bit 5bit 5bit 5bit 6bit

op

命令の基本操作。従来からの命令操作コード( opcode オペコード)と呼ばれる

rs

第1のソース・オペランドのレジスタ

rt

第2のソース・オペランドのレジスタ

rd

デスティネーション・オペランドのレジスタ。結果を収める先

shamt

シフト量

この用語の意味は第4章で

funct

機能

命令操作フィールドのバリエーションを表す

機能コード( function code )と呼ばれることがある

上に示したフィールドよりも長いフィールドが必要とする命令があると問題が発生する

レジスタを2つと、アドレスを1つ指定する必要がある

ソース・オペランドのレジスタ

デスティネーション・レジスタ

メモリのベース・アドレス

もしアドレスの指定に5ビットのフィールドのどれかを当てるとすると lw 命令内の定数は 2^5 つまり 32 に限定されてしまう

この定数は大きな配列またはデータ構造から要素を選択するために使用されるので、要素の数は32よりはるかに大きいことが多い。5ビットでは小さすぎる

ここで、すべての命令長を同じにしたいという要求と、命令形式を1つにとどめたいという要求とが、両立しなくなるという問題が発生する

設計原則3

優れた設計には適度な妥協が必要である

MIPS の設計者が選択した妥協案は、すべての命令長を同じに保つことだった

命令の種類によって命令形式が異なる場合が発生する

2つの命令形式

R 形式

R フォーマット

レジスタ用

table:R Format

field No. 1 2 3 4 5 6

filed name op rs rt rd shamt funct

bit 6bit 5bit 5bit 5bit 5bit 6bit

I 形式

I フォーマット

データ転送命令用

table:I Format

field No. 1 2 3 4

filed name op rs rt address

bit 6bit 5bit 5bit 16bit

データ転送命令中の定数をオフセット( offset )

アドレスを得るために加えるレジスタをベース・レジスタ( base register )と呼ぶ

オフセット 32 は address フィールドへ入れられる

lw 命令では rt フィールドは転送されるデータを受け取るデスティネーション・レジスタを表すことになる

table:exp3.3.2

field No. 1 2 3 4

filed name op rs rt adress

decimal 35 19 8 32

MIPS 命令の符号化

table: MIPS Instruction Encoding

命令 形式 op rs rt rd shamt funct address

add R 0 レジスタ レジスタ レジスタ 0 32 使用せず

sub R 0 レジスタ レジスタ レジスタ 0 34 使用せず

lw I 35 レジスタ レジスタ 使用せず 使用せず 使用せず アドレス

sw I 43 レジスタ レジスタ 使用せず 使用せず 使用せず アドレス

「レジスタ」は 0 ~ 31 のレジスタ番号

「アドレス」は 16ビット のアドレス

「使用せず」はそのフィールドを使用しないことを意味する

code:exp3.4.2.c

code:exp3.4.2.asm

この3つの命令に対する MIPS の機械語コード

まず10進数を使用して表現する

table:exp3.4.2.1

op rs rt rd shamt address / funct

35 9 8 --- --- 1200

0 18 8 8 0 32

43 9 8 --- --- 1200

2進数を使用して表現する

table:exp3.4.2.2

op rs rt rd shamt address / funct

10 0011 0 1001 0 1000 --- --- 0000 0100 1011 0000

00 0000 1 0010 0 1000 0 1000 0 0000 100000

10 1011 0 1001 0 1000 --- --- 0000 0100 1011 0000

最初の命令と最後の命令がほとんど同じであることに注目。違うのは左から3番目のビットのみ

根本事項

今日のコンピュータは2つの基本原理に基づいて設計されている

1. 命令は数値として表現される

2. プログラムをメモリ中に格納して、数値と同様に読み書きすることができる

この方式の発明により、コンピュータの世界に「魔法のランプの精 ジニー」が呼び出された

https://gyazo.com/f3e15f3dac0435b0a452fc67318df748

CODv2 3.5 条件判定用の命令

Preliminary Discussion of the Logical Design of an Electronic Computing Instrument

電子計算機の論理設計に関する予備的考察

Arthur W. Burks, Herman H. Goldstine, and John von Neumann

2 September 1947

自動的な計算機の真価は、命令系統を繰り返し実行できること、しかもその繰り返し回数を計算結果に基づいて決められることにある。繰り返し処理が完了したならば、それに続いて別の命令を実行させる。したがって、多くの場合、2通りの命令の流れを用意し、その前にどちらのルーチンを実行するかを判定する命令を置く必要がある。判定は、数値の符号(マシンでの取り扱い上は、ゼロを正とみなす)に基づいて行うようにすればよい。この意味は、条件命令を導入するということである。これによって、指定した数値の符号に応じて、2つのルーチンから適切な方を選んで実行させることが可能になる

3.5. The utility of an automatic computer lies in the possibility of using a given sequence of instructionsrepeatedly, the number of times it is iterated being either preassigned or dependent upon the results of thecomputation. When the iteration is completed a different sequence of orders is to be followed, so we must,in most cases, give two parallel trains of orders preceded by an instruction as to which routine is to befollowed. This choice can be made to depend upon the sign of a number (zero being reckoned as plus formachine purposes). Consequently, we introduce an order (the conditional transfer order) which will,depending on the sign of a given number, cause the proper one of two routines to be executed.Frequently two parallel trains of orders terminate in a common routine. It is desirable, therefore, to orderthe control in either case to proceed to the beginning point of the common routine. This unconditionaltransfer can be achieved either by the artificial use of a conditional transfer or by the introduction of anexplicit order for such a transfer.

一般に、プログラミング言語においては、条件を表すために if 文を使用する

それに加えて、必要に応じて、 goto 文とラベルを使用する

MIPS のアセンブリ言語には条件判定用の命令が2つ用意されている

beq 命令

beq register1, register2, L1

bne 命令

bne register1, register2, L1

この2つの命令を条件分岐( conditonal branch )命令と呼ぶ。

code:exp3.5.1.c

if (i == j) goto L1;

f = g + h;

L1: f = f - i;

f, g, h, i, j は変数である

$s0, $s1, $s2, $s3, $s4

5つの変数を $s0 から $s4 の5つのレジスタに割り付けるとして、このコードのコンパイルした結果の MIPS のアセンブリ・コードを示せ

code:exp3.5.1.asm

beq $s3, $s4, L1 # i == j なら L1 に分岐

add $s0, $s1, $s2 # f = g + h (i == j ならスキップ)

L1: sub $s0, $s0, $s3 # f = f - i (常に実行される)

1行目

最初の C ステートメントは、2つの変数が等しいかどうかをチェック。等しければ3行目(減算)に分岐する

この2つのオペランド i, j は共にレジスタ上にあるので branch if eqauls に対応する

(ラベル L1 は後で定義する)

2行目

次のステートメントは、単一の演算を行っている。単一の命令にコンパイルできる

3行目

最後のステートメントも、単一の命令にコンパイルできる。問題は、条件分岐する際にスキップできるようにアドレスを指定する方法である

このラベルが beq 命令によって前方向に参照される。

ラベル L1 は減算命令のアドレスに対応する

重要：

アセンブラはこのようにラベルを使用することにより、コンパイラやアセンブリ言語プログラマが、分岐先アドレスの計算にわずらわされずに済むようにしている

ロードおよびストアの際にアセンブラがアドレス算出を行っているのも同様の趣旨である

コンパイラは元のコードにない分岐を生成したり、ラベル付けを行ったりすることがよくある。

ラベルや分岐を明示的に書く手間が省けることが、高水準プログラミング言語でプログラムを記述する利点の一つであり、コーディング時間が短縮される理由の一つである

code:exp3.5.2.c

if (i == j) f = g + h; else f = g - h;

code:exp3.5.2.1.c

if (i == j) f = g + h;

else f = g - h;

変数 f, g, h, i, j はそれぞれ

レジスタ $s0, $s1, $s2, $s3, $s4 に割り付けられる

code:exp3.5.2.1.asm

bne $s3, $s4, Else # i != j なら Else に分岐

add $s0, $s1, $s2 # f = g + h (i != j ならスキップ)

j Exit # Exit へジャンプ

Else: sub $s0, $s1, $s2 # f = g - h (i == j ならスキップ)

Exit:

if 文のフローチャート

code:graph3.7.mmd

flowchart TD

a{"if(i == j)"}

a -- "then\n(i ==j)" --> b("f = g + h")

a -- "else\n(i != j)" --> c("f = g - h")

b --> d("exit:")

c --> d("exit:")

1行目

bne 命令を使う

条件を逆にチェックした方がコードの効率が高くなる

if 文のすぐ後ろ、 then の部分を実行するコードを飛び越すように分岐する

(ラベル Else は後で定義する)

2行目

単一の演算を行う

3行目

2行目の処理が終了したら if 文の最後まで飛ぶ必要がある

この分岐を無条件分岐( unconditional branch )と呼ぶ

j 命令

(ラベル Exit は後で定義する)

4行目

if 文の else 部分にあたる代入文も単一の演算をおこなう

ただしラベル Else が必要

5行目

else 部分の命令の後に Exit というラベルを付けて、コンパイルの済んだ if-then-else コードの終了を示す必要がある

beq 命令を適用した場合

2回ジャンプを使う / ラベルを2個使う

ステップが1つ多い

code:exp3.5.2.2.asm

beq $s3, $s4, Then # i == j なら Then に分岐

j Else # Else へジャンプ (i == j ならスキップ)

Then: add $s0, $s1, $s2 # f = g + h

j Exit # Exit へジャンプ

Else: sub $s0, $s1, $s2 # f = g - h (i == j ならスキップ)

Exit:

code:exp3.5.3.c

i = i + j;

if(i != h) goto Loop;

配列 A は100個の要素からなる配列

配列 A のベース・アドレスはレジスタ $s5 に収められている

変数 g, h, i, j はそれぞれ

レジスタ $s1, $s2, $s3, $s4 に割り付けられる

参考

g = h + A[i];

最初の命令にラベル Loop を追加する必要がある

6行目の命令で i に j を加算

最後の命令で i != h の場合に分岐して Loop に戻る

code:exp3.5.3.asm

Loop: add $t1, $s4, $s4 # 2 * i の結果を一時レジスタ $t1 に代入

add $t1, $t1, $t1 # 4 * i の結果を一時レジスタ $t1 に代入(オフセットを合成)

add $s3, $s3, $s4 # i = i + j

bne $s3, $s2, Loop # i != h なら Loop へ戻る

末尾に分岐がある命令列はコンパイルする上で非常に重要なので基本ブロック( basic block )という呼び名を与えられている

それはブロック中には分岐も分岐ラベルもない一続きの命令であるが、末尾に条件分岐があることと、冒頭にラベルがあることは許される

コンパイルの最初の段階の作業の一つはプログラムを基本ブロックに分割することである

code:exp3.5.4.c

i = i + j;

変数 i, j, k はそれぞれ

レジスタ $s3, $s4, $s5 に割り付けられる

code:exp3.5.4.asm

Loop: add $t1, $s3, $s3 # 2 * i の結果を一時レジスタ $t1 に代入

add $t1, $t1, $t1 # 4 * i の結果を一時レジスタ $t1 に代入(オフセットを合成)

add $s3, $s3, $s4 # i = i + j

j Loop # Loop へジャンプ

Exit:

slt 命令

code:slt.asm

slt $t0, $s1, $s2

code:slt.c

if($s1 < $s2)

$t0 = 1;

else

$t0 = 0;

$s1 は $s2 より小さい?

true

$t0 == 1

false

$t0 == 0

MIPS のコンパイラは、

slt と beq と bne の各命令

およびレジスタ $zero を読むことによって常に得られる固定値 0

これらを使用して、すべての相対条件判定ルーチンを生成する

具体的な相対条件は

等しい

等しくない

より小

以下

より大

以上

変数 a が変数 b よりも小さいことを判定して、真であればラベル LT( Less than ) へ分岐するコード

変数 a, b は

レジスタ $s0, $s1 に割り付けられている

code:exp3.5.5.c

if( a < b) goto LT

LT:

code:exp3.5.5.asm

slt $t0, $s0, $s1 # a < b のとき( $s0 < $s1 のとき)、 $t0 に 1 が設定される

bne $t0, $zero, LT # $t0 が 0 と等しくないとき( a < b のとき)、 Less に分岐する

j Exit

LT:

Exit:

参考

code:exp3.5.5.2.c

if ( a <= b ) goto LE

LE:

code:exp3.5.5.2a.c

if ( a == b ) goto LE

else if ( a < b ) goto LE

LE:

code:exp3.5.5.2a.asm

bne $s0, $s1, Else

j LE

Else: slt $t0, $s0, $s1

bne $t0, $zero, LE

j Exit

LE:

Exit:

case 文 / switch 文

1つの変数の値に基づいて、いくつかの場合(ケース)の処理の中から1つを選択する

こうしたスイッチを実現する方法

if-then-else 構文をいくつも繋げた形での条件判定

それぞれの場合の処理のアドレスをテーブル(表)にして、そのどれをとるか示すインデックスに従って該当処理へジャンプする

ジャンプ・アドレス表( jump address table )

コード中のラベルに対応するアドレスを表す語の配列

jr 命令

ジャンプ・レジスタ命令 jr ( jump register )

jr $t0

code:exp3.5.6.c

switch (k) {

case 0: f = i + j; break;

case 1: f = g + h; break;

case 2: f = g - h; break;

case 3: f = i - j; break;

}

変数 f ~ k は

レジスタ $s0 ~ $s5 に割り付けられている

レジスタ $t2 には値 4 が設定されている

k の値をチェックして、どれかのケースに該当するか確認する

0 <= k <= 3

いずれのケースにも該当しない場合には switch 文の出口に飛ぶ

k < 0 || k > 4

メモリ中の連続する4つの語にラベル L0, L1, L2, L3 に対応するアドレスが保持されており、そのベース・アドレスが $t4 に収められているとする

code:exp3.5.6.asm

slt $t3, $s5, $zero # k < 0 かチェックする。 k < 0 ならば $t3 == 1 をセット

bne $t3, $zero, Exit # k < 0 ( $t3 == 1 つまり $t3 != 0 )ならば Exit へジャンプ

slt $t3, $s5, $t2 # k > 4 かチェックする。 k > 4 ならば $t3 ==1 をセット

bne $t3, $zero, Exit # k > 4 ( $t3 == 1 つまり $t3 != 0 )ならば Exit へジャンプ

add $t1, $s5, $s5 # 2 * k の結果を一時レジスタ $t1 に代入

add $t1, $t1, $t1 # 4 * k の結果を一時レジスタ $t1 に代入(オフセットを合成)

jr $t0 # レジスタ $t0 に基づいてジャンプ

L0: add $s0, $s3, $S4 # k == 0 であれば f = i + j

j Exit # Exit へジャンプ

L1: add $s0, $s1, $s2 # k == 1 であれば f = g + h

j Exit # Exit へジャンプ

L2: sub $s0, $s1, $s2 # k == 2 であれば f = g - h

j Exit # Exit へジャンプ

L3: sub $s0, $s3, $S4 # k == 3 であれば f = i - j

Exit: # Switch 文の終了

CODv2 3.6 コンピュータ・ハードウェア内での手続きのサポート

手続き、サブルーチン

プログラムを構成する1つの方法

コードの再利用を可能にする

プログラマはタスクの一部分だけに専念することができる

パラメータ

手続きと、プログラムの残りの部分の障壁の役割を果たす

プログラムを通じて、値を受け渡し、結果を返す働きをする

プログラムの6つの手順

1. 手続きからアクセスできる場所にパラメータを置く

2. 手続きに制御を移す

3. 手続きに必要なメモリ資源を入手する

4. 必要なタスクを実行する

5. 呼出し元のプログラムからアクセスできる場所に結果を置く

6. 制御を元の場所に戻す

レジスタ数32個のうち MIPS で手続き呼出しに用いるレジスタ

4個の引数レジスタ

手続きにパラメータを渡すために使用

2個の戻り値レジスタ

手続きから結果の値を返すために使用

1個の戻りアドレス・レジスタ

制御を元に戻すために使用

ジャンプ&リンク命令

jump-and-link

jal ProcedureAddress

手続き専用の命令

手続きアドレス( Procedure Address )にジャンプすると同時に、次の命令のアドレスをレジスタ $ra に退避する

戻りアドレス( return address )

呼出した手続きから呼出し元に戻る「リンク」が形成されていることを意味する

レジスタ $ra

戻りアドレスが必要なのはプログラム内のいくつもの場所から同じ手続きが呼出されることがあるため

プログラム内蔵方式のプログラムでは現在実行中の命令のアドレスを保持するレジスタが必要

命令アドレス・レジスタ( instruction address register ) と呼んだ方が意味がよくわかる

手続きの呼出し

(呼出した jal 命令自体のアドレスが PC なので1ステップ分、プラスしている?)

呼出し元への戻り

jr $ra

戻りアドレス・レジスタの指すアドレスへジャンプする

手続きの流れ

呼出し側( caller )のプログラムは、

パラメータ値をレジスタ $a0 ~ $a3 に収め、

被呼出し側( callee )のプログラムは、

計算を実行し

結果をレジスタ $v0 ~ $v1 に収め、

もっと多くのレジスタを使用する場合

スピル・アウト

スタック( stack )

プッシュ( push )

ポップ( pop )

スタック・ポインタ( stack pointer ) $sp

MIPS のソフトウェアではスタック専用に特別のレジスタを割り当てているこれをスタック・ポインタ( stack pointer ) $sp という

使用目的は、呼び出し側で必要とされるレジスタを退避することにある

歴史的ないきさつ

スタックは高いアドレスから低いアドレスに向かって伸びる

プッシュするとき

スタック・ポインタから減算

スタックは伸びる

ポップするとき

スタック・ポインタに加算

スタックは縮む

「例題3.2.2 : C の複雑な代入文の MIPS へのコンパイル」を手続きにする

code:exp3.2.2a.c

f = (g + h) - (i + j);

「例題3.2.2 : C の複雑な代入文の MIPS へのコンパイル」をレジスタにしたもの

「例題3.3.1 : レジスタを使用した C の代入文のコンパイル」

code:exp3.2.2a.c

f = (g + h) - (i + j);

code:exp3.6.1.c

int leaf_example(int g, int h, int i, int j)

{

int f;

f = (g + h) - (i + j);

return f;

}

本設では以降、 4, 8, 12 といった定数を加算または減算できるものとする

( MIPS のアセンブリ言語で定数をどのように処理するかは 3.8節 )

パラメータ変数の g, h, i, j は、

$a0 ~ $a3 に相当する

変数 f は $s0 に相当する

コンパイルされたプログラムの先頭には手続きのラベルがくる

code:exp3.6.1.asm

leaf_example:

一時レジスタの退避

手続きによって使用されるレジスタを、最初に退避する

プッシュ

「例題3.3.1 : レジスタを使用した C の代入文のコンパイル」のアセンブリ・コード

変数 f, g, h, i, j をそれぞれレジスタの $s0, $s1, $s2, $s3, $s4 に割り付けている

一時レジスタ $t0, $t1 を割り当ている

code:exp3.3.1a.asm

add $t0, $s1, $s2

add $t1, $s3, $s4

sub $s0, $t0, $t1

一時レジスタ $t0, $t1 の2つを使用する

これに $s0 を含めて、合計3つのレジスタを使用する

手続きに入る前に、使用するレジスタの値の分スタックをプッシュし、一時レジスタの古い値を退避する

code:exp3.6.1.asm

sub $sp, $sp, 12 # スタックに3語分のスペースを作る

sw $t1, 8($sp) # レジスタ $t1 を後の使用に備えて退避する

sw $t0, 4($sp) # レジスタ $t0 を後の使用に備えて退避する

sw $s0, 0($sp) # レジスタ $s0 を後の使用に備えて退避する

手続きの呼出し前(a)、呼出し中(b)、呼出し後(c)のスタックの様子

https://gyazo.com/fbac6ac529b7a9ff62daafb4c5ab1aea

例題3.3.1 のステートメントを MIPS のレジスタに合わせて書き換える

パラメータ変数の g, h, i, j は、

引数レジスタ $a0 ~ $a3 に相当する

変数 f は $s0 に相当する

code:exp3.6.1.asm

add $t0, $a0, $a1 # g + h が一時レジスタ $t0 に代入される

add $t1, $a2, $s3 # i + j が一時レジスタ $t1 に代入される

sub $s0, $t0, $t1 # f = (g + h) - (i + j) がレジスタ $s0 に代入される

戻り値

f の値を返すために、それを戻り値レジスタ $v0 にコピーする

code:exp3.6.1.asm

add $v0, $s0, $zero # f を返す( $v0 = $s0 + 0 )

一時レジスタの復元

呼出し元に制御を戻す前に、退避しておいた一時レジスタの古い値を復元し、スタックを元の値にポップする

code:exp3.6.1.asm

lw $s0, 0($sp) # 呼出し側のためにレジスタ $s0 を復元する

lw $t0, 4($sp) # 呼出し側のためにレジスタ $t0 を復元する

lw $t1, 8($sp) # 呼出し側のためにレジスタ $t1 を復元する

add $sp, $sp, 12 # スタックから3語分のスペースを除く

戻りアドレスを用いて、ジャンプ・レジスタ命令を実行して、手続きを終える

code:exp3.6.1.asm

jr $ra # 呼出し元のルーチンにジャンプして戻る

これらをまとめると

code:exp3.6.1a.asm

leaf_example:

sub $sp, $sp, 12 # スタックに3語分のスペースを作る

sw $t1, 8($sp) # レジスタ $t1 を後の使用に備えて退避する

sw $t0, 4($sp) # レジスタ $t0 を後の使用に備えて退避する

sw $s0, 0($sp) # レジスタ $s0 を後の使用に備えて退避する

add $t0, $a0, $a1 # g + h が一時レジスタ $t0 に代入される

add $t1, $a2, $s3 # i + j が一時レジスタ $t1 に代入される

sub $s0, $t0, $t1 # f = (g + h) - (i + j) がレジスタ $s0 に代入される

add $v0, $s0, $zero # f を返す( $v0 = $s0 + 0 )

lw $s0, 0($sp) # 呼出し側のためにレジスタ $s0 を復元する

lw $t0, 4($sp) # 呼出し側のためにレジスタ $t0 を復元する

lw $t1, 8($sp) # 呼出し側のためにレジスタ $t1 を復元する

add $sp, $sp, 12 # スタックから3語分のスペースを除く

jr $ra # 呼出し元のルーチンにジャンプして戻る

MIPS の2種類のレジスタ

例題3.6.1 では使用する全てのレジスタについて、使用時に、その値を退避、復元するものとした

一時レジスタの中には使用されていないものもありうる

退避、復元する必要のあるレジスタを明確化

MIPS では以下の2つのタイプのレジスタを用意している

一時レジスタ $t0 ~ $t9

10個

手続き呼び出しの際に、被呼出し側で保存しない

退避レジスタ $s0 ~ $s7

8個

手続き呼び出しの際に、保存されなければならない

使用する場合、被呼出し側で退避、および復元する

この簡単な規約によって、レジスタのスピル・アウトが削減される

$t0 は一時レジスタと呼ぶ

退避レジスタと呼ぶ

入れ子にされた手続き

他の手続きを呼出さない手続きをリーフ( leaf )手続きと呼ぶ

手続きが、手続きを呼ぶ

手続きが、自分自身のクローンを呼ぶ

再帰型手続き

手続きが、リーフではない手続きを呼ぶ

手続きが、手続きを呼ぶ手続き、を呼ぶ

請け、孫請け、曾孫請け

入れ子にされた手続きの場合のレジスタの扱い

例えば

その際に引数レジスタ $a0 に引数の値 3 が入れられる

その際には引数レジスタ $a0 に引数の値7が入れられる

この際に手続き A はまだタスクを完了していないので、

レジスタ $a0 の使用に関して2つの手続き間で競合が発生する

戻りアドレス・レジスタ $ra についても競合が発生する

その際に $ra に呼出し元のメインプログラムへの戻りアドレスが入れられる

その際に $ra に呼出し元の手続き A への戻りアドレスが入れられる

策を講じないと手続き A は呼出し元のメインプログラムへ制御を戻せなくなる

1つの解決案

保存されるべき他のすべてのレジスタをスタック上にプッシュする

呼び出し側

被呼出し側

code:exp3.6.2.c

int fact(int n)

{

if(n < 1)

return(1);

else

return(n * fact(n - 1));

}

1 や 8 といった定数を加算、減算できるものとする

最初に手続きのラベルを示す

code:exp3.6.2.asm

fact:

sub $sp, $sp, 8 # スタック上に2語分のスペースを確保する

sw $ra, 4($sp) # 戻りアドレス・レジスタを退避

sw $a0, 0($sp) # 引数 n (引数レジスタ $a0 )を退避

条件分岐( if-then-else)

条件判定( if )

code:exp3.6.2.asm

slt $t0, $a0, 1 # n < 1 のとき( $a0 < 1 のとき)、$t0 に 1 が設定される

beq $t0, $zero, L1 # $t0 が 0 と等しいとき( n >= 1 のとき)、 L1 に分岐

n < 1 の場合( then )

手続き fact は 1 を返す

値レジスタに 1 を入れる

1 を 0 に加算して、その和を値レジスタ $v0 に代入する

code:exp3.6.2.asm

add $v0, $zero, 1 # 1 を返す

スタック上に退避されている2つの値をポップする

n < 1 の場合、 $a0 と $ra は不変(未使用)であるので、それらの命令をスキップできる

戻りアドレスにジャンプする

code:exp3.6.2.asm

jr $ra # 呼出し元の jal 命令の後ろに戻る

n >= 1 の場合( else )

手続きのラベルを示す

ラベル L1

n を 1 繰り下げる ( n - 1)

繰り下げた値を用いて再び fact を呼び出す(再帰)

code:exp3.6.2.asm

L1:

sub $a0, $a0, 1 # 引数レジスタ $a0 に n - 1 を代入する

jal fact # 引数レジスタ $a0 ( n -1 ) を用いて、手続き fact を呼び出す

呼び出した fact から戻るための処理を行う

戻りアドレスと引数を復元する

スタック・ポインタを戻す

code:exp3.6.2.asm

lw $a0, 0($sp) # 引数 n (引数レジスタ $a0 )を復元

lw $ra, 4($sp) # 戻りアドレス・レジスタを復元

add $sp, $sp, 8 # スタックから2語分のスペースを落とす

乗算命令を使用できるものとする

(第4章で説明する)

code:exp3.6.2.asm

mul $v0, $a0, $v0 # n * fact(n - 1) を返す

最後にこれ自身の手続き fact から戻りアドレスにジャンプして戻る

code:exp3.6.2.asm

jr $ra # 呼出し元の jal 命令の後ろに戻る

これらをまとめると

code:exp3.6.2a.asm

fact:

sub $sp, $sp, 8 # スタック上に2語分のスペースを確保する

sw $ra, 4($sp) # 戻りアドレス・レジスタを退避

sw $a0, 0($sp) # 引数 n (引数レジスタ $a0 )を退避

slt $t0, $a0, 1 # n < 1 のとき( $a0 < 1 のとき)、$t0 に 1 が設定される

beq $t0, $zero, L1 # $t0 が 0 と等しいとき( n >= 1 のとき)、 L1 に分岐

add $v0, $zero, 1 # 1 を返す

jr $ra # 呼出し元の jal 命令の後ろに戻る

L1:

sub $a0, $a0, 1 # 引数レジスタ $a0 に n - 1 を代入する

jal fact # 引数レジスタ $a0 ( n -1 ) を用いて、手続き fact を呼び出す

lw $a0, 0($sp) # 引数 n (引数レジスタ $a0 )を復元

lw $ra, 4($sp) # 戻りアドレス・レジスタを復元

add $sp, $sp, 8 # スタックから2語分のスペースを落とす

mul $v0, $a0, $v0 # n * fact(n - 1) を返す

jr $ra # 呼出し元の jal 命令の後ろに戻る

手続き呼び出しの間に、保持されるレジスタと保持されないレジスタ

https://gyazo.com/03013b39454be75c0523f3f015ae11a8

「スタック・ポインタより上のスタックの内容を保持する」

スタック・ポインタ $sp より上のスタックの内容を保持するには、被呼出し側が $sp より上には書き込まないようにしている

1. スタック・ポインタ・レジスタ $sp の内容を保持するために、被呼出し側で引いた値と(プッシュ)、同じ値を加える(ポップ)ようにしている

2. その他のレジスタの内容を保持するために(使用された場合には)、それらをスタック上に退避し、そこから復元している

これらの操作によって、呼出し側がスタックからロードしたときに、スタックにストアしたのと同じデータが再び得られることが保証される

なぜならば、被呼出し側では $sp の内容を保持するようにしており、かつ呼出し側が書き込んだスタックの部分を(つまり呼出し側の $sp より上の部分を)、被呼出し側では変更しないようにしているから

https://gyazo.com/fbac6ac529b7a9ff62daafb4c5ab1aea

新しいデータ用のスペースの割当て

(なにいっているのか全然わからん)

手続きフレーム( procedure frame )、またはアクティベーション・レコード( activation record )

手続き内の変数であるが、レジスタに割り付けられないものを格納するためにもスタックが使用される

配列、データ構造

スタックのうちで手続きによって退避されたレジスタ、ローカル変数(配列、データ構造)が収められている領域を手続きフレーム、アクティベーション・レコードと呼ぶ

下図は、手続き呼び出し時の、前(a)、途中(b)、後(c)のスタックの状態

フレーム・ポインタ( frame pointer )

ローカル変数は低位アドレス方向に追加される

したがって、メモリ中のローカル変数(配列、データ構造)を参照するオフセットはその位置に応じて変化し得る

フレーム・ポインタは手続き内でローカルなメモリを参照する際の安定した基準となる

図3.12 手続き呼出しの前 (a), 途中(b), 後(c) のスタックの割当ての図解

https://gyazo.com/04ae84c49ce0baac1952340da27340a8

フレームの先頭の語は退避された引数レジスタであることが多い。

退避されるすべてのレジスタおよびメモリに常駐するローカル変数を収容するために,スタックの大きさが調整される。

プログラムの実行中にスタック・ポインタは変化する可能性があるので、プログラマにとっては安定しているフレーム・ポインタを通じて変数を参照する方 が容易である。

ただし、スタック・ポインタを使用しても、多少のアドレス演算を加えることによって、同様のことが可能である。

手続き内にスタック上に置くローカル変数がない場合には、コンパイラはフレーム・ポインタの設定と復元を省略して、時間を節約する。

MIPS のアセンブリ言語用のレジスタの使用規約

図3.13 MIPS のレジスタ規約

https://gyazo.com/3413e5662b6d27ac77b1a89ffe989775

補足 : パラメータが5つ以上ある場合

4個

MIPS のソフトウェア規約ではフレーム・ポインタのすぐ上のスタック(低位のアドレス)を使用することにしている

補足 : jal 命令

C の変数は記憶内(メモリ中)の1つのロケーションである

その解釈はタイプ( type )と記憶クラス( storage class )に応じて異なる

タイプについては第4章で

タイプ

整数

文字

記憶クラス

C には2種類の記憶クラスがある

自動変数( automatic variable )

自動変数は手続きの内部だけで存在し、手続きが終了する際に破棄される

静的変数( static variable )

静的変数は手続きの開始および終了を超えて存在する

すべての手続きの外で宣言された C の変数は静的とみなされる

キーワード "static" を使用して宣言された変数も同様

それ以外の変数はすべて自動変数である

静的データへのアクセスを単純化するために MIPS ソフトウェアでは別のレジスタを予約している

グローバル・ポインタ( global pointer )

$gp

静的データがメモリ中のどこに割当てられるかは3.9節で

CODv2 3.7 数値を超えて

コンピュータは数値を処理するものとして発明された

商用に供されるようになると、コン`ピュータはすぐにテキスト処理に使用されるようになった

ASCII

American Standard Code for Information Interchange

情報交換用米国標準コード

https://gyazo.com/f21c698f19d69ced433ee2bd2d95428b

ASCII は1バイトのサイズ

実際には7ビット分

0~127

MIPS で語( data )は4バイトのサイズを持つ

ここまでで扱った命令は4バイトのデータを扱っている

sw 命令、 lw 命令は語(4バイト)をストア、ロードする

ASCII を扱うには sw 命令、 lw 命令はサイズが大きい(?)

命令をいくつか並べて使用すれば語からバイトを抽出できる(?)が、

MIPS ではバイトを転送する特別の命令を用意している

ロード・バイト命令

load byte 命令

$sp はスタック・ポインタ

lb 命令は、メモリから1バイトをロードして、レジスタの右端(一番小さい桁)の8ビットに収める

ストア・バイト命令

store byte 命令

sb 命令は、レジスタの右端の8ビットを取り出して、メモリに収める

文字列( string )

文字はいくつか並べて使用するのが普通

文字列の長さは可変

文字列の長さを表す方法

1. 文字列の最初の文字を、文字列の長さを示すために使用する

2. 付随する変数に文字列の長さを保持する(データ構造として)

3. 文字列の最後の文字に、文字列の終端を表す特定の文字を使用する

C 言語は3番めの方法

文字列の終端を値がゼロのバイトで示す

null

\0

code:exp3.7.1.c

void strcpy(char x[], char y[])

{

int i;

i = 0;

i = i + 1;

}

1や4のような定数を加算、減算できるものと想定する

(なぜこれに退避レジスタを用いるのか?)

最初に手続きのラベルを示す

code:exp3.7.1.asm

strcpy:

sub $sp, $sp, 4 # スタック上に1語分のスペース(4バイト)を確保する(プッシュする)

sw $s0, 0($sp) # $s0 をスタックに退避

変数 i を初期化する

配列 y の最初の要素を指すオフセット

code:exp3.7.1.asm

add $s0, $zero, $zero # i = 0 + 0 : オフセット 0

while ループ

i を4倍する必要がないのは、配列 y は、語(4バイト)の配列ではなく、バイトの配列だから

code:exp3.7.1.asm

L1:

code:exp3.7.1.asm

code:exp3.7.1.asm

変数 i を繰り上げる

文字がゼロ、文字列の最後でなければループの頭に戻る(ラベル L1)

code:exp3.7.1.asm

add $s0, $s0, 1 # i = i + 1

code:exp3.7.1.asm

lw $s0, 0($sp) # $s0 を復元

add $sp, $sp, 4 # スタックから1語分のスペース(4バイト)を落とす(ポップする)

jr $ra # 呼出し元の jal 命令の後ろに戻る

これらをまとめると

code:exp3.7.1a.asm

strcpy:

sub $sp, $sp, 4 # スタック上に1語分のスペース(4バイト)を確保する(プッシュする)

sw $s0, 0($sp) # $s0 をスタックに退避

add $s0, $zero, $zero # i = 0 + 0 : オフセット 0

L1:

add $s0, $s0, 1 # i = i + 1

lw $s0, 0($sp) # $s0 を復元

add $sp, $sp, 4 # スタックから1語分のスペース(4バイト)を落とす(ポップする)

jr $ra # 呼出し元の jal 命令の後ろに戻る

コンパイラはリーフ手続きを見つけると、まず一時レジスタを使用し、それをすべて使い切ってから、退避する必要のあるレジスタを使用する

CODv2 3.8 MIPS のその他のアドレシング方式

オペランドのアクセス方法があと2通りある

1. 小さな定数へのアクセスを高速化するためのもの

2. 分岐を効率よく行うためのもの

定数すなわち既値のオペランド

プログラム中では定数が演算に使用されることが多い

配列の次の要素を指すためのインデックスの繰り上げ

ループに繰り返し回数のカウント

入れ子になった手続き呼び出しにおけるスタックの調整

などなど

ここまでで示した命令しかない場合、定数を使用するときにはメモリから値をロードしなければならない

(その定数はプログラムのロード時にメモリに収められるはず)

このような場合、レジスタ $sp に定数4を加えるコードは下記のようになる

ここで AddrConstant4 は定数4のメモリ・アドレスを表すものとする

code:exp3.8.0.asm

lw $t0, AddrConstant4($zero) # $t0 = 4 (定数 4 のメモリ・アドレスにレジスタ $zero の固定値 0 を合算したアドレスから定数をロード)

add $sp, $sp, $t0 # $sp = $sp + $t0 ( $t0 = 4 )

メモリから定数を取り出さずに済ませるためには、新しいカタチの演算命令が必要

addi 命令

add immediate

オペランドの1つを定数とし、その定数を命令自体の中にもつ

「規則性を重んずべし」の指針に従い、この命令ではデータ転送命令( lw / sw )と同じ I 形式を用いる

I 形式の I は既知( immediate )という用語にちなんだもの

レジスタ $sp に定数4を加えるコードは下記のようになる

code:exp3.8.1.asm

addi $sp, $sp, 4

上記の命令の機械語コードを10進数で表現する

table:addi1

field No. 1 2 3 4

filed name op rs rt immediate

decimal 8 29 29 4

スタック・ポインタのレジスタ番号: 29

これを機械語(2進数)で表現すると

table:addi2

field No. 1 2 3 4

binary 001000 11101 11101 0000 0000 0100

bit 6bit 5bit 5bit 16bit

既値、定数のオペランドは比較においてもよく使われる

code:slt.asm

slt $t0, $s1, $s2 # $s1 < $s2 のときに $t0 = 1

レジスタ $zero の値は常に 0 なので、 0 との比較は簡単

code:slt2.asm

slt $t0, $s1, $zero # $s1 < zero のときに $t0 = 1

code:slt3.asm

slt $t0, $zero $s1 # $s1 > zero のときに $t0 = 1

slt 命令の既値版があればいい

slti 命令

set on less than immediate

code:slti.asm

slti $t0, $s2, 10 # s2 < 10 のときに $t0 = 1

これと同様に bne 命令を続ければ分岐が可能

code:slti2.asm

slti $t0, $s2, 10 # s2 < 10 のときに $t0 = 1

bne $t0, $zero L1 # $t0 が 0 でないとき( $s2 < 10 のとき)、ラベル L1 へ分岐

設計原則4

一般的な場合を高速化せよ

定数が16ビットを超える場合について

オペランドが定数となるケースは頻繁に発生する

したがって、定数を演算命令の一部に組み込めば、メモリから定数をロードするよりも、はるかに処理が速くなる

定数は小さいことが多く、ほとんど16ビットに収まる

が、16ビットを超える場合

lui 命令

load upper immediate

この命令は定数の上位16ビットをレジスタに入れるためのもの

それに続けて別の命令を使用して、その定数の下位16ビットを設定することができる

code:lui.asm

lui $t0, 255

これを機械語(2進数)で表現すると

$t0 はレジスタ 8

table:lui

field No. 1 2 3 4

filed name op rs rt immediate

decimal 7 0 8 255

binary 001111 00000 01000 0000 0000 1111 1111

bit 6bit 5bit 5bit 16bit

table:$t0

ビット 上位16ビット 下位16ビット

binary 0000 0000 1111 1111 0000 0000 0000 0000

lui 命令は 16ビットの既値定数フィールドの値を、対象とするレジスタ $t0 の左側部分の16ビットに転送し、そのレジスタの右側16ビットをゼロで埋める

https://gyazo.com/038c38b1746d57201b8a35d4a41b9286

以下の32ビットの定数をレジスタ $s0 にロードする MIPS アセンブリ・コードを示せ

2進数 : 0000 0000 0011 1101 0000 1001 0000 0000

16進数 : 00 3D 09 00

10進数 : 4,000,000

上位16ビット

2進数 : 0000 0000 0011 1101

16進数 : 00 3D

10進数 : 61

下位16ビット

2進数 : 0000 1001 0000 0000

16進数 : 09 00

10進数 : 2304

code:exp3.8.2.asm

lui $s0, 61 # レジスタ $s0 の上位16ビットに定数 61 をロードする

addi $s0, $s0, 2304 # レジスタ $s0 (の下位16ビット)に定数 2304 を加える

コンパイラまたはアセンブラのどちらかが、大きな定数を分割してレジスタ上に設定し直す作業を受け持たなければならない

MIPS ではアセンブラが受け持つ方式を用いる

既値フィールドの大きさに関する制限は、既値をとる命令中の定数の場合だけでなく、ロードとストアの際のメモリ・アドレスを表す場合にも問題になる

アセンブラが受け持つ場合には、長い値を作るための一時アドレスが必要となる

$at

MIPS の機械語シンボル表現は、もはやハードウェアに制約されるのではなく、アセンブラ開発者が選択した事柄に制約される

分岐とジャンプにおけるアドレシング

最も単純なアドレシングはジャンプ命令のものである

この命令形式を J 形式と呼ぶ

ジャンプ命令のステートメント

code:j.asm

j 10000 # 10000番地にジャンプ

これに対するアセンブラ・コードは下記のようになる

table:J 形式

field No. 1 2

filed name op target address

decimal 2 10000

bit 6bit 26bit

ジャンプ命令の op コード(命令操作コード) の値は 2

ジャンプ先アドレス用には、 6bit の op フィールドを除く 26bit を用いることができる

2^26 = 67,108,864

条件分岐命令のステートメント

条件分岐分岐命令の場合は、ジャンプ命令とは異なり、分岐先アドレスの他にオペランドを2つ指定しなければならない

code:bne.asm

bne $s0, $s1, Exit # $s0 と $s1 が等しくないときにはラベル Exit へ分岐する

これをアセンブルすると、

table:I 形式

field No. 1 2 3 4

filed name op rs rt address

decimal 5 8 21 Exit

bit 6bit 5bit 5bit 16bit

このように分岐先アドレス用には16ビットしか残されない

2^16 = 65,536

これはプログラムの大きさが 2^16 を超えることができないことを意味する

あまりにも小さすぎる

解決策

解決策として分岐先アドレスに加算するレジスタを指定する方法が考え出された

プログラム・カウンタ = レジスタ + 分岐先アドレス

2^32 までの大きさのプログラムに条件分岐を適用できる

残る問題は、どのレジスタを使用するか

解決策の答えは条件分岐の使われ方を検討することによって得られる

条件分岐はループおよび if 文の中で使われる

分岐先は分岐命令の近くにある公算が大きい

例：gcc および spice (とは? LISP コンパイラ?) では全条件分岐の約半分の分岐先は16命令以内である

プログラム・カウンタ( PC )には現在の命令のアドレスが記憶されている

分岐先アドレスに加えるレジスタとして、このプログラム・カウンタ( PC )を使用すれば、現在の命令から ± 2^15 語の範囲で分岐することができる

相対アドレス?

2^15 なのは正負の符号化のため?

課題：2ビットの演算がわかっていない

ほとんどのループや if 文は 2^16 語よりもずっと小さい

プログラム・カウンタ( PC ) はこの目的に最適である

PC 相対アドレシング

PC-relative addressing

この形式の分岐アドレシングを PC 相対アドレシング( PC-relative addressing )と呼ぶ

補足：

ハードウェアにとっては PC を早期に繰り上げて、次の命令を指しておくと便利

MIPS では現在の命令のアドレス( PC )を基準にするのではなく、次の命令( PC + 4 )のアドレスを基準にして相対アドレシングを行う

ジャンプ&リンク命令の場合

条件分岐命令の場合、分岐先は条件分岐命令の近くである公算が大きいが、

ジャンプ&リンク命令( jamp-and-link )では、呼び出す対象の手続きが呼び出し元の近くにあるという保証はない

したがって、手続き呼び出しの場合には、別の形式のアドレシングを適用する

疑似直接アドレシング

ジャンプ&リンク命令( jal )およびジャンプ命令( j )では、どちらも J 形式を適用して長いアドレスの指定を可能にしている

code:3.8.1.c

i = i + j;

レジスタ 22

それぞれレジスタ 19, 20, 21

code:exp3.8.1.asm

Loop: add $t1, $s3, $s3 # 2 * i の結果を一時レジスタ $t1 に代入

add $t1, $t1, $t1 # 4 * i の結果を一時レジスタ $t1 に代入(オフセットを合成)

add $s3, $s3, $s4 # i = i + j

j Loop # Loop へジャンプ

Exit:

このループの開始アドレスが 800000 であるとする

このループの MIPS 機械語コードはどうなるか

MIPS のアセンブリ言語でのレジスタ

レジスタ 16 ~ 23

レジスタ 8 ~ 15

MIPS 命令の符号化

beq, bne, j, jal を追記

table: MIPS Instruction Encoding

命令 形式 op rs rt rd shamt funct address

add R 0 レジスタ レジスタ レジスタ 0 32 使用せず

sub R 0 レジスタ レジスタ レジスタ 0 34 使用せず

lw I 35 レジスタ レジスタ --- --- --- アドレス

sw I 43 レジスタ レジスタ --- --- --- アドレス

beq I 4 レジスタ レジスタ --- --- --- アドレス

bne I 5 レジスタ レジスタ --- --- --- アドレス

j J 2 --- --- --- --- --- ターゲット・アドレス

jal J 3 --- --- --- --- --- ターゲット・アドレス

table:exp3.8.1

address \ field 1 2 3 4 5 6

80000 0 19 19 9 0 32

80004 0 9 9 9 0 32

80008 0 9 22 9 0 32

80012 35 9 8 0 --- ---

80016 5 8 21 8 --- ---

80020 0 19 20 19 0 32

80024 2 80000 --- --- --- ---

80028

MIPS では

バイト・アドレス方式をとっている

順番に並んだ語のアドレスは1語のバイト数、4バイト刻みでずれる

5行目( 80016 )の bne 命令では、

完全なアドレス( 80028 )の代わりに、

また、現在の命令( 80016 )に 12 を加える代わりに、

次の命令のアドレス( 80020 )に8を加える相対アドレシングを行っている

最後の行のジャンプ命令では、ラベル Loop に対応する完全なアドレス( 80000 )を指定している

バイト数と語数

MIPS の命令長はすべて4 バイトである

そこで MIPS では、 PC 相対アドレシングにおいて、次の命令までのバイト数の代わりに語数を使用する

これにあわせて上記 exp3.8.1 を書き換えると、

table:exp3.8.1a

address \ field 1 2 3 4 5 6

80000 0 19 19 9 0 32

80004 0 9 9 9 0 32

80008 0 9 22 9 0 32

80012 35 9 8 0 --- ---

80016 5 8 21 2 --- ---

80020 0 19 20 19 0 32

80024 2 80000 --- --- --- ---

80028

アドレス( 80016 )にある bne 命令中のアドレス・フィールドの値は 8 ではなく 2 となる

このように、バイト数の代わりに語数を使用することで、分岐先をさらに遠くまで伸ばすことができる

16ビット・フィールド( I 形式)がバイト・アドレスではなく語アドレスを表すと解釈すれば4倍、遠くまで分岐できる

table:I 形式

field No. 1 2 3 4

filed name op rs rt address

decimal 5 8 21 Exit

bit 6bit 5bit 5bit 16bit

条件分岐の分岐先はたいてい近くにある

しかしときには分岐先が非常に遠くて 2^16 ビットでは表せないことがある

そのような場合には、大きな定数の場合と同様、アセンブラが助け舟を出す

具体的には、分岐先へ飛ぶ無条件ジャンプ命令を挿入して、挿入したそのジャンプを飛ばすか否かに条件判定を変える

レジスタ $s0 とレジスタ $s1 が等しいときに、ラベル L1 に分岐する

code:exp3.8.2a.asm

beq $s0, $s1, L1

もっと遠くへ分岐可能な命令列で上記命令を置き換える

beq 命令のアドレス・フィールドは 16 ビット

j 命令のアドレス・フィールドは 26ビット

code:exp3.8.2b.asm

bne $s0, $s1, L2

j L1

L2:

j 命令のアドレス・フィールドは 26 ビット

table:J 形式

field No. 1 2

filed name op target address

decimal 2 10000

bit 6bit 26bit

疑似直接アドレシング

補足：

ジャンプ命令中の 26 ビット・フィールドも語アドレスを表す

これは28ビット分のバイト・アドレスに相当する(語アドレスの4倍、1語は4バイト、2ビットで4倍が表現される)

table:2bit

number/field no. 1 0

0 0 0

1 0 1

2 1 0

3 1 1

プログラム・カウンタ PC は32ビットなので、どこかから4ビットを補わなければならない

MIPS のジャンプ命令は PC の下位28ビットだけをジャンプ命令中のアドレスに置換し、上位4ビットは元のままとする

ローダおよびリンカはアドレス境界を超えてプログラムを配置しないようにしなければならない

256Mバイト (6400万命令) ?

2^28 ビット?

さもなければジャンプ命令をジャンプ・レジスタ命令および他の命令で置き換えて、レジスタに32ビット・アドレス全体をロードするようにしなければならない

言っていることはわかるが、アドレス境界の数値の大きさがよくわからない。保留

MIPS のアドレシング・モードのまとめ

https://gyazo.com/176b6c4c174b170a5910ef629a252e06

5つのアドレシング・モード

1. 既値アドレシング

2. レジスタ・アドレシング

3. ベース相対アドレシング

4. PC 相対アドレシング

5. 疑似直接アドレシング

オペランドは緑で網掛けして示す

モード1の場合は、オペランドは命令自体の下位16ビットである

モード2のオペランドはレジスタである

モード3のオペランドはメモリ中にある

ロードとストアにはメモリ上の、バイト、半語、語にアクセスするバージョンがあることに注意

語 : lw / sw

半語 : lh / sh (いまのところ説明なし)

バイト : lb / sb

モード4とモード5では、メモリ中の命令のアドレスを指すことに注意

モード5の場合は、26ビットのアドレスを PC の上位ビットと連結する

PC : プログラム・カウンタ

2025/09/02 だいぶ間が空いてしまったので、復習する

上の「ベース相対アドレシング」がなんなのかすっかり忘れてしまった

ベース相対アドレシング

https://gyazo.com/eaedb56f7e8687a46828241f1b3db60f

ロード命令 lw とストア命令 sw

"Adress" って書いてあるからすっと入ってこなかったけど lw / sw ではオフセットの定数が入っている

1ワード(語) は 4バイト

"Register" にはメモリ上のベースアドレスが入っている

データ転送命令中の定数をオフセット( offset )

アドレスを得るために加えるレジスタをベース・レジスタ( base register )と呼ぶ

オフセット 32 は address フィールドへ入れられる

lw 命令では rt フィールドは転送されるデータを受け取るデスティネーション・レジスタを表すことになる

table:exp3.3.2

field No. 1 2 3 4

filed name op rs rt adress

decimal 35 19 8 32

ベース相対アドレシングの、メモリ上のバイトにアクセスするバージョン

ロード・バイト命令 lb と ストア・バイト命令 sb

文字列データ ASCII を扱う

ロード・バイト命令

load byte 命令

$sp はスタック・ポインタ

lb 命令は、メモリから1バイトをロードして、レジスタの右端(一番小さい桁)の8ビットに収める

ストア・バイト命令

store byte 命令

sb 命令は、レジスタの右端の8ビットを取り出して、メモリに収める

例題3.7.1 : C の文字列の使い方を示す文字列コピー手続きのコンパイル

PC 相対アドレシング

https://gyazo.com/23d4653d2f95923f2d693d923c1c6614

beq 命令、 bne 命令

分岐先のアドレスとして、プログラム・カウンタ( PC ) (現在の命令のアドレス(実際には次の命令のアドレス))を基準にした相対アドレスを用いる

相対アドレスは正負の向き

PC 相対アドレシングにおいて、次の命令までのバイト数の代わりに語数を使用する

例題3.8.1 : 機械語での分岐オフセットの表記

疑似直接アドレシング

https://gyazo.com/e9214a6c9936a511867d65b388bb5d5e

MIPS のジャンプ命令は PC の下位28ビットだけをジャンプ命令中のアドレスに置換し、上位4ビットは PC を元のまま用いる

ジャンプ命令中の 26 ビット・フィールドも語アドレスを表す

「26ビットのアドレスを PC の上位ビットと連結する」

機械語とアセンブリ言語の対応

フォーマット

R 形式

R フォーマット

レジスタ用

table:R Format

field No. 1 2 3 4 5 6

filed name op rs rt rd shamt funct

bit 6bit 5bit 5bit 5bit 5bit 6bit

bit No. 31-26 25-21 20-16 15-11 10-6 5-1

I 形式

I フォーマット

データ転送命令用

table:I Format

field No. 1 2 3 4

filed name op rs rt address

bit 6bit 5bit 5bit 16bit

bit No. 31-26 25-21 20-16 15-1

J 形式

J フォーマット

ジャンプ命令用

table:J Format

field No. 1 2

filed name op target address

bit 6bit 26bit

bit No. 31-26 25-1

MIPS の機械語とアセンブリ言語の対応

図3.18a

op (31:26)

https://gyazo.com/94f420bd363cd0d5179ce4db8b7500d3

図3.18b

op(31:26)=010000 (TLB),rs (25:21)

https://gyazo.com/e2987727e2000285d71d20639c1dbd6e

図3.18c

op (31:26)=000000 (R), funct (5:0)

https://gyazo.com/39c0a05cedc33ab7d8c043b1d5d1fe51

table:exp3.8.3

bit No. 31-28 27-24 23-19 18-16 15-12 11-8 7-4 3-0

binary 0000 0000 1010 1111 1000 0000 0010 0000

復号

table:exp3.8.3a

bit No. 31-26 25-6 5-3 2-0

binary 000000 00101011111000000000 100 000

上記、 図3.18a より

op (31:26)=000000

R 形式

図3.18c より

funct(5:0)=100 000

故にこのバイナリ表現は add 命令である

残りの部分を復号するためにフィールドの値を見る

R 形式は、

table:R Format

field No. 1 2 3 4 5 6

filed name op rs rt rd shamt funct

bit 6bit 5bit 5bit 5bit 5bit 6bit

bit No. 31-26 25-21 20-16 15-11 10-6 5-1

これに合わせると

table:exp3.8.3b

field No. 1 2 3 4 5 6

filed name op rs rt rd shamt funct

bit No. 31-26 25-21 20-16 15-11 10-6 5-0

binary 000000 00101 01111 10000 00000 100000

decimal 0 5 15 16 0 32

rs フィールドの10進数は 5 、 rt フィールドの10進数は 15 、 rd フィールドの10進数は16

( shamt フィールドは未使用)

https://gyazo.com/3413e5662b6d27ac77b1a89ffe989775

rs

第1のソース・オペランドのレジスタ

rs はレジスタ番号 : 5 、引数レジスタ : $a1

rt

第2のソース・オペランドのレジスタ

rt はレジスタ番号 : 15 、一時レジスタ : $t7

rd

デスティネーション・オペランドのレジスタ。結果を収める先

rd はレジスタ番号 : 16 、退避レジスタ : $s0

以上からこの命令のアセンブリ言語表現は以下のようになる

code:3.8.3asm

add $s0, $a1, $t7 # 引数レジスタ $a1 と一時レジスタ $t7 を加算して、退避レジスタ $s0 に代入

第3章で示した MIPS の命令のフォーマット

図3.19

https://gyazo.com/abdf49622141288f1de49048b124d7c5

第3章で提示した MIPS アーキテクチャ

図3.20a MIPS オペランド

https://gyazo.com/7e4b6e971c6e0665badeb6178b36b826

図3.20b MIPS アセンブリ言語

https://gyazo.com/e3fb5bc6511d58f7fb3437dc4270cc52

CODv2 3.11 配列とポインタの対比

CODv2 3.12 実例：PowerPCと80×86の命令

CODv2 3.13 誤信と落とし穴

CODv2 3.14 おわりに

end